package DynamicProgramming.Medium;

public class LC0005 {
    /**
     * 动态规划法，时间复杂度N^2
     * 中心扩散法的时间复杂度也是N^2，但实际上往往能实现高得多的性能；该算法留待日后实现。
     */
    public String longestPalindrome(String s) {
        int N = s.length();
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[N][N + 1]; // dp[i,m]表示从位置i开始，长度为m的子串是否为回文串
        int recordStart = 0, recordN = 1;
        for (int n = 1; n <= N; n++) {
            for (int start = 0; start <= N - n; start++) {
                if (n == 1) dp[start][n] = true;
                else if (n == 2) dp[start][n] = chars[start] == chars[start + 1];
                else {
                    if (chars[start] != chars[start + n - 1]) dp[start][n] = false;
                    else dp[start][n] = dp[start + 1][n - 2];
                }

                if (dp[start][n]) {
                    recordStart = start;
                    recordN = n;
                }
            }
        }

        return s.substring(recordStart, recordStart + recordN);
    }

    /**
     * 中心扩散法。从每个可能的中心位置出发向两侧扩散，检查以该位置为中心的回文串有多长。尽管这种算法的复杂度也为N^2，但考虑到可能存在大量回文串长度
     * 远短于完整字符串s，实际的耗时会比动态规划法更短（后者为严格的N^2）；此外，这种方法在空间复杂度上也更有优势。选取中心位置时，要注意对于偶数
     * 长度的回文串，它的中心是两个字符（或者说是两个字符中间的位置）。
     */
    public String longestPalindromeDiffuse(String s) {
        // 标记中心位置的指针。两指针重合，表示奇数长度的字串；两指针相邻，表示偶数长度的字串。
        int fast = 0, slow = 0;
        int N = s.length();
        int maxLength = 1;
        String ret = s.substring(0, 1);
        char[] chars = s.toCharArray();
        while (fast < N && slow < N) {
            int length, left, right;
            if (fast == slow) {
                length = 1;
                left = fast - 1;
                right = fast + 1;
            }
            else {
                length = 0;
                left = slow;
                right = fast;
            }
            while (left >= 0 && right < N && chars[left] == chars[right]) {
                length += 2;
                left--;
                right++;
            }
            if (length > maxLength) {
                maxLength = length;
                ret = s.substring(left + 1, right);
            }

            if (fast == slow) fast++;
            else slow++;
        }

        return ret;
    }

    public static void main(String[] args) {
        String s = "babad";
        LC0005 solver = new LC0005();
        System.out.println(solver.longestPalindrome(s));
    }
}
